/**
 * @param {number} n
 * @return {string[][]}
 * 输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
 */
var solveNQueens = function (n) {
  let datas = []
  const getRule = data => {
    if (data.length === 1) {
      return true
    }
    let indexArr = data.map(item => item.indexOf('Q'))
    if ([...new Set(indexArr)].length !== indexArr.length) {
      // 纵向存在Q
      return false
    }
    let len = indexArr.length - 1
    let len1 = indexArr.length - 1
    let lastItem = indexArr[indexArr.length - 1]
    let lastItem1 = indexArr[indexArr.length - 1]
    while (len > 0) {
      // 斜线上存在Q
      len--
      lastItem--
      lastItem1++
      len1--
      if (indexArr[len] === lastItem) return false
      if (indexArr[len1] === lastItem1) return false
    }
    // while (len1 > 0) {
    //   // 斜线上存在Q
    //   lastItem1++
    // }
    return true
  }
  const getData = (data, m) => {
    const arr = []
    arr.length = n
    arr.fill('.')
    arr[m] = 'Q'
    data.push(arr)

    if (getRule(data)) {
      let i = n
      if (data.length === n) {
        const joinData = data.map(item => item.join(''))
        datas.push(joinData)
        return data
      }
      while (i > 0) {
        getData([...data], i - 1)
        i--
      }
    }
  }
  if (n === 1) {
    return [['Q']]
  }
  let t = 0
  while (t < n) {
    let newData = []
    getData(newData, t)
    t++
  }
  return datas
}
console.log(solveNQueens(4))
